In general, the present invention relates to computer vision and image processing and more specifically, the mapping of an image stored in a computer-teadable format onto a computer generated surface. Basic techniques have been proposed for the limited purpose of obtaining a flattened computerized image or representation of a convoluted surface such as the cortical surface of a mammalian brain to aid in the visualization of this very complex structure. The computer graphics process known as xe2x80x98texture mappingxe2x80x99 has been limited to the process of transferring a two-dimensional image (a digitized photograph or artificially produced picture or graphic) onto a three-dimensional computer generated surface. However, here more particularly, the invention relates to a novel technique of conformally mapping any image that can be stored in a computer-readable format as two-, three-, or four- dimensional dynamic coordinate data, onto two-, three-, or a dynamically-varying family of surfaces, respectively. Of particular interest is the application of a very unique flattening function (derived from numerically approximating a selected partial differential equation, PDE) to surface data of an original digitized image. The surface data can comprise triangulated or other-shaped elements, cells, patches, segments, or portions thereof, that has been extracted as necessary from original image data to remove handles, holes, self-intersections, and so on, to produce a generally smooth manifold upon which the flattening function can be performed to produce a flattening map. The novel computerized mapping technique of the invention generally preserves angles of the original image as mapped and the mapping performed is bijective (onto and one to one).
Prior techniques have been proposed to obtain a flattened/planar representation of a xe2x80x98realxe2x80x99 object such as the complex cortical surface of a human brain (as described in the medical imaging literature): The collaborators hereof have addressed limitations to these proposed/known methods. For example, in one published paper the scientific authors fit a parameterized deformable digitized surface of a brain whose topology is mappable onto a sphere and then xe2x80x98flattenxe2x80x99 the sphere to create a planar map by using spherical coordinates. In other algorithms proposed for the purpose of xe2x80x98flatteningxe2x80x99 a brain image using quasi-isometrics and quasi-conformal flattenings approaches, the scientists started with a triangulated representation of a given image of the cortical surface and employ a relaxation method to discretely minimize an energy functional. Unfortunately, bijectivity cannot be preserved in when using this prior approach, and in particular, there is a chance that the tiny triangle shaped patched of the triangulated surface will flip during the quasi-isometrics or quasi-conformal process (and if any number of the tiny triangles do flip, the resulting flattened representation is not true and, in fact, can become quite distorted). By way of review for reference, bijection occurs when: A mapping f from a set A onto a set B which is both an injection and a surjection; that is, for every element b of B there is a unique element a of A for which f(a)=b.
The technique of the invention is very distinguishable from prior mapping approaches. As it will be better appreciated, the novel technique provides for an explicit construction of the bijective conformal equivalence on a continuous model of the surface being mapped, and only then is there a move toward the discrete implementation. Key and surprising differences include: the flattening function performed according to the invention is preferably obtained as the solution of a selected second-order elliptic partial differential equation (PDE) on the surface to be flattened; this selected PDE can then readily be approximated using a finite element approximation on a triangulated (or other discrete-element shaped) representation of the original surface; and further, the novel flattening function performed on a constructed set of surface data (extracted and/or smoothed to reduce effects of aliasing, as desired), can be derived from identifying solutions to two sparse systems of linear equations treated using the conjugate gradient method. In the event the surface on which the flattening function of the invention is performed is constructed as a triangulated surface, one can use a known fast segmentation method to adequately represent the iso-surface as a triangulated surface of a digitized synthetic or xe2x80x98realxe2x80x99 image of an object (e.g., a cortical surface).
The ingenious technique described herein produces a mapped image, or a series of dynamically-mapped sequential images that represent changes in time to the original image (for example, a beating human heart or when digestive byproduct moves through a colon causing the colon surfaces to change shape), that locally preserves certain important characteristics (shape and angles) of each original image. And, unlike known prior graphics flattening algorithms or computerized graphics texture mapping processes, original image characteristics are preserved even when the surface on which the image is being mapped is quite different from the surface of the original image (for example, an image of brain white matter conformally maps quite clearly onto a sphere and a spherical image of the earth is readily mapped onto an odd synthetic xe2x80x98blobxe2x80x99 shape). The instant invention permits the construction, among other things, of a bijective conformal equivalence from a given image""s surface (generally having holes or handles removed) onto a sphere, onto a planar domain (such as a rectangle), or onto other preselected two-, three-, or a dynamically-varying family of surfaces. The conformal flattening process maps the surface in a manner that preserves both the angles of and, locally, the shape of the original image.
In order to more-fully understand the invention, details of the rigorous mathematical analysis which has been done of this new technique follow along with illustrations of several conformal mapping examples. As one will better appreciate, one can employ graphics coloring techniques after performing the novel method of producing a flattening map of complex, time-varying digitized surfaces to create beautiful motional graphical images for a wide variety of applicationsxe2x80x94from medial diagnostic, product and process design, to pure entertainment. The flattening function and conformal mapping can be performed, with an original digitized image stored as two-, three-, and four-dimensional dynamic coordinate data onto a two-, three-, plus the dynamically-varying family of surfacesxe2x80x94thus, the invention is not limited to 2-D (planar) to 3-D texture mapping of still images.
It is a primary object of this invention to provide a computerized apparatus and associated method and program code on a storage medium, for producing a flattening map of a digitized image, whether this image is initially synthetically produced as discrete data (for example, a computer generated graphic) or originates as quasi-discrete image data of a real object (e.g., produced as a result of a digital photo, an x-ray, diagnostic scan, document scan, and so on)xe2x80x94and whether the original image data is stored as two-, three-, or four-dimensional dynamic coordinate data. The flattening map can be conformally mapped onto a computer generated surface (whether 2-D, 3-D, or any dynamically-varying family of surfaces) that can be displayed on a computer-assisted display apparatus in communication with a processor. The apparatus and associated method and program code include constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image, and performing a flattening function on the first set of data to produce the flattening map.
Certain advantages of providing the novel computerized apparatus and associated new method and program code stored on a computer readable storage medium, as described and supported hereby, are as follows:
(a) The apparatus and method can produce not only a single mapped image for viewing and/or printout in hard copy form, as well as for electronically storage, but also can produce a series of dynamically-mapped sequential images that represent changes in time to the original image (for example, watching a beating human heart or monitoring brain activity or colon activity using functional magnetic resonance data), that locally preserves certain important characteristics (shape and angles) of each original image.
(b) Application Versatilityxe2x80x94The invention can be used for analysis within a wide range of environments such as medical applications (e.g., for image-guided surgery and non-invasive diagnostic imaging to better view images of complex anatomy, plus real-time/dynamic monitoring and treatment of patients); product and process design research and development for analysis/viewing composite structures and composite materials such as those encountered in integrated circuit and printed circuit board fabrication; product design and analysis of vehicle component s and assemblies (including vehicles that travel over ground, through the air, into outer space, etc.); creating automatic angle-preserving 3-D texture mapping onto synthetic surfaces to create xe2x80x98compositexe2x80x99 graphic images that can be used in the computer-animation of movies, cartoons, virtual-reality systems/devices, image registration for educational and entertainment purposes; creating conformally mapped graphic images using 2-D, 3-D, and dynamically-varying family of surfaces for specific purposes such as non-invasive virtual colonoscopy to detect presence of pathologies, shading of geographic, atmospheric, galactic, and weather maps, and so on.
(c) Simplicity and Versitility of usexe2x80x94With relative ease, the new computerized apparatus and associated program code can be run with, and the new method can be installed onto, readily operated, updated, and uninstalled from existing computer equipment running any of a number of master control programs such as any UNIX- or LINUX-, WINDOWS(trademark)-, WINDOWS NT(trademark)-, and MACINTOSH(copyright)-based operating system.
(d) Design Flexibilityxe2x80x94A flattening map produced according to the invention from extracted discrete surface-element data (such as the tiny triangle patches of a triangulated surfacexe2x80x94e.g., the xe2x80x98blobxe2x80x99 illustrated in FIG. 5) to which the novel flattening function has been applied, can be used alone to produce valuable surface-flattening information about an original image, or it can be used to create a wide variety of conformally mapped surfaces; for example, a portion of one or several original images may be extracted, or the whole image can be extracted, to automatically in a piece-meal fashion reconstruct a composite mapped image made of xe2x80x98realxe2x80x99 and synthetic parts of different original (well-preserved) image components. Further, the flattening function can be employed to produce a flattening map of a single selected original image (such as the cortical structure in FIG. 4) and conformally mapped onto several different computer-generated shapes such as a sphere, a blob, a cylinder, and a square.
(e) Speed of Applicationxe2x80x94The novel use of the Laplace-Beltrami operator (designated by the Greek symbol, xcex94) contained within the two sparse systems of linear equations computed to create the flattening map (and the application of newly-identified boundary conditions to derive these linear equations), allows for much faster and more-efficient conformal mappings of original images (whether of convoluted real objects or synthetic images) onto convoluted (or simple) computer-generated surfaces.
(f) Process Simplificationxe2x80x94The use of infinitely small (in a xe2x80x98mathematical sensexe2x80x99) discrete surface-elements or patches (regardless of shape) to closely approximate the original image surface, plus the straightforward calculations made of a solution for a second-order elliptic partial differential equation (PDE) derived after having, first, identified, applied, and simplified a series of key complex mathematical theories and algorithms on each surface-element, has simplified in a novel and unexpected way the process of creating a well-preserved flattened map of an original image.
(g) Reliability and robustnessxe2x80x94The novel flattening procedure has been shown to be highly robust to various types of transformations including affine deformations of the pre-image data as well as triangle decimation on the image surface.
Briefly described, once again, the invention includes a computerized apparatus and associated method and program code on a storage medium, for producing a flattening map of a digitized image, whether this image is initially synthetically produced as discrete data (for example, a computer generated graphic) or originates as quasi-discrete image data of a real object (e.g., produced as a result of a digital photo, an x-ray, diagnostic scan, document scan, and so on)xe2x80x94and whether the original image data is stored as two-, three-, or four-dimensional dynamic coordinate data. The digitized image may be of a variety of real objects such as a cortical structure (any outer portion of a mammalian organ or other structure, e.g. a brain, adrenal gland, colon, and so on), considered quasi-discrete data, or the image may be one that comprises purely computer-generated discrete data, which can include a composite of many synthetic images. In the case where the image is of a real object, it may be desirable to extract surface-element data from the image""s surface to eliminate handles, holes and other disruptions and provide a generally smooth manifold upon which to perform the flattening function; and further it may be necessary to smooth the quasi-discrete data of the real object""s surface to reduce effects of aliasing. Once produced, a flattening map can be conformally mapped onto the computer generated surface (whether 2-D, 3-D, or any of the dynamically-varying family of surfaces) for display on a computer-assisted display apparatus in communication with a processor. The apparatus and associated method and program code include constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image, and performing a flattening function on the first set of data to produce the flattening map.
Features that further distinguish the apparatus, method, and program code of the invention from conventional techniques, include: The flattening function includes computing, for the discrete surface-elements, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE). These constructed surface-elements can be representative of triangulated areas, random-shaped areas or patches, surface points, pixels, sub-pixels, cells, sub-cells, segments, and sub-segments, and so on. The two systems of linear equations are preferably formulated by applying a finite-element approximation comprising a sparse matrix, the selected PDE preferably comprises the expression                               Δ          ⁢                      xe2x80x83                    ⁢          z                =                              (                                          ∂                                  ∂                  u                                            -                              i                ⁢                                  ∂                                      ∂                    v                                                                        )                    ⁢                      δ            p                                              Eq.  (1)            
thus, the two systems of linear equations can comprise the expressions
Dx=axe2x80x83xe2x80x83Eq. (2)
Dy=xe2x88x92b; andxe2x80x83xe2x80x83Eq. (3)
the flattening function can further comprise the identification of values for the variables DPQ, aQ and bQ using at least the following expressions:                                           D                          P              ⁢                              xe2x80x83                            ⁢              Q                                =                                    -                              1                2                                      ⁢                          {                                                cot                  ⁢                                      xe2x80x83                                    ⁢                  ∠                  ⁢                                      xe2x80x83                                    ⁢                  R                                +                                  cot                  ⁢                                      xe2x80x83                                    ⁢                  ∠                  ⁢                                      xe2x80x83                                    ⁢                  S                                            }                                      ,                  P          ≠          Q                                    Eq.  (4)                                          D                      P            ⁢                          xe2x80x83                        ⁢            P                          =                  -                                    ∑                              P                ≠                Q                                      ⁢                          D                              P                ⁢                                  xe2x80x83                                ⁢                Q                                                                        Eq.  (5)                                                      a            Q                    -                      i            ⁢                          xe2x80x83                        ⁢                          b              Q                                      =                  {                                                                      0                  ,                                                                              Q                  ∉                                      {                                          A                      ,                      B                      ,                      C                                        }                                                                                                                                                                                          -                        1                                                                    "LeftDoubleBracketingBar"                                                  B                          -                          A                                                "RightDoubleBracketingBar"                                                              +                                          i                      ⁢                                                                        1                          -                          θ                                                                          "LeftDoubleBracketingBar"                                                      C                            -                            E                                                    "RightDoubleBracketingBar"                                                                                                      ,                                                                              Q                  =                  A                                                                                                                                                1                                              "LeftDoubleBracketingBar"                                                  B                          -                          A                                                "RightDoubleBracketingBar"                                                              +                                          i                      ⁢                                              θ                                                  "LeftDoubleBracketingBar"                                                      C                            -                            E                                                    "RightDoubleBracketingBar"                                                                                                      ,                                                                              Q                  =                  B                                                                                                                          i                    ⁢                                                                  -                        1                                                                    "LeftDoubleBracketingBar"                                                  C                          -                          E                                                "RightDoubleBracketingBar"                                                                              ,                                                                              Q                  =                  C                                                                                        Eq.  (6)            
As identified above, and further according to the invention, computing a solution to each of the two systems, namely Eqs. (2) and (3), results in the piecewise linear functional expressions                     x        =                              ∑            Q                    ⁢                                    x              Q                        ⁢                          φ              Q                                                          Eq.  (7)                                y        =                              ∑            Q                    ⁢                                    y              Q                        ⁢                          φ              Q                                                          Eq.  (8)            
such that x and y are conformally mapped according to the expression z=x+iy onto a preselected computer-generated surface for display. Further, in the case where the digitized image changes shape over time, the first set of data can be constructed to further comprise a series of corresponding sets of data over time such that the flattening function is performed on each of the series of data sets to produce a corresponding series of the flattening maps.
Also characterized is a method for producing a flattening map of a digitized image, comprising the steps of: constructing a first set of data with a processor, this data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image; and performing a flattening function on the first set of data to produce the flattening map. The flattening function to comprise computing, for each discrete surface-element, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE). Also characterized is a computer executable program code on a computer readable storage medium for producing a flattening map of a digitized image. The program code includes: a first program sub-code for constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image; and a second program sub-code for performing a flattening function on the first set of data to produce the flattening map. The second sub-code includes instructions for computing, for each discrete surface-element, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE). The method and program code can further include a third program sub-code for conformally mapping the flattening map onto a computer-generated 3D surface for display on a computer-assisted display apparatus. The further distinguishing features set forth above, will be readily appreciated in connection with the following description.